import java.util.Arrays;

/**
 * 堆排序
 * 1.构造大顶堆（大顶堆：每个节点的值都大于等于两个子节点的值）
 *      并不是真的构造，只是在 res 数组中操作
 *      比如 res[1] 的两个子节点就是 res[3] 和 res[4]
 *      左子节点：i * 2 + 1
 *      左子节点：i * 2 + 2
 * 2.大顶堆构造完成后，遍历大顶堆数组，每一次将堆顶元素，
 *      即 res[0] 与数组末尾元素交换，同时 len - 1
 *      交换后，还需要执行构造的操作，保证堆顶元素是 [0, len] 中的最大值
 *
 * 技巧：大顶堆用于升序排列，小顶堆用于降序排序
 */
public class HeapSort {
    private static int len;
    private static int[] res;

    public static int[] heapSort(int[] nums) {
        res = Arrays.copyOf(nums, nums.length);
        len = res.length;
        // 构造大顶堆
        buildMaxHeap();
        // 构造完成，从堆中取元素，添加到结果数组中
        for (int i = len - 1; i > 0; i--) {
            // res[0] 最大元素与数组末尾元素替换
            swap(0, i);
            // 若不减 1，则 res[len - 1] 的最大值元素，还会成为堆顶元素
            // 可以理解为：每放回一个元素到 res 中，即大顶堆的节点少一个
            len --;
            // 继续保证 res[0] 是 [0, len] 中的最大元素
            heapify(0);
        }
        return res;
    }

    public static void buildMaxHeap() {
        // 使父节点的值大于等于两个子节点即可
        // 优化：只有一半的节点有子节点，故只有一半的节点需要与子节点比较大小
//        for (int i = len - 1; i >= 0; i--) {
        for (int i = len / 2; i >= 0; i--) {
            heapify(i);
        }
    }

    public static void heapify(int i) {
        int maxIdx = i;
        int left = i * 2 + 1;
        if (left < len && res[maxIdx] < res[left]) {
            // 左子节点存在，并且父节点值小于子节点值，变更 maxIdx
            maxIdx = left;
        }
        int right = i * 2 + 2;
        if (right < len && res[maxIdx] < res[right]) {
            // 左子节点存在，并且父节点值小于子节点值，变更 maxIdx
            // 注意：此时的 res[maxIdx] 也有可能是 left 索引上的值
            // 因为父节点值已经与左子节点比较过了
            maxIdx = right;
        }
        if (maxIdx != i) {
            // 需要交换
            swap(i, maxIdx);
            // 原本父节点的值交换到子节点后，该值有可能还小于其子节点的值
            // 那么就不符合大顶堆的要求，即需要递归进行 heapify 操作
            // 保证父节点的值大于等于子节点的值，若小于就需要继续替换下去
            // 递归保证 maxIdx 节点不会小于子节点的值
            heapify(maxIdx);
        }
    }

    public static void swap(int i, int j) {
        int temp = res[i];
        res[i] = res[j];
        res[j] = temp;
    }
}
